package com.leetcode.partition5;

import java.io.*;
import java.util.HashMap;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2022/3/16 9:35
 */
public class LC432全O1的数据结构 {

    private static final int N = 50010;
    private static PriorityQueue heap = new PriorityQueue();

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int m = Integer.parseInt(reader.readLine());
        while (m-- > 0) {
            String[] ss = reader.readLine().split(" ");
            int op = Integer.parseInt(ss[0]);
            if (op == 1) {
                inc(ss[1]);
            } else if (op == 2) {
                dec(ss[1]);
            } else if (op == 3) {
                writer.write(getMaxKey() + "\n");
            } else {
                writer.write(getMinKey() + "\n");
            }
            writer.flush();
        }
        writer.flush();
    }

    public static void inc(String key) {
        heap.incr(key);
    }

    public static void dec(String key) {
        heap.decr(key);
    }

    public static String getMaxKey() {
        return heap.getMax();
    }

    public static String getMinKey() {
        return heap.getMin();
    }

    private static class PriorityQueue {
        //堆中维护大顶堆和小顶堆，同时支持指定元素删除和指定元素变化
        private Node[] maxEle = new Node[N], minEle = new Node[N];
        private Map<String, Integer> maxMap = new HashMap<>(N), minMap = new HashMap<>(N);
        private int size;

        //第k个元素上浮，大顶堆
        private void maxSwim(int k) {
            int cur = k, pi = k >> 1;
            while (cur > 1 && maxEle[cur].w > maxEle[pi].w) {
                swap(maxEle, maxMap, cur, pi);
                cur = pi;
                pi >>= 1;
            }
        }

        //第k个元素上浮，小顶堆
        private void minSwim(int k) {
            int cur = k, pi = k >> 1;
            while (cur > 1 && minEle[cur].w < minEle[pi].w) {
                swap(minEle, minMap, cur, pi);
                cur = pi;
                pi >>= 1;
            }
        }

        //第k个元素下沉，大顶堆
        private void maxSink(int k) {
            int cur = k;
            while (cur <= size / 2) {
                int l = cur << 1, r = cur << 1 | 1;
                if (maxEle[l].w > maxEle[cur].w || (r <= size && maxEle[r].w > maxEle[cur].w)) {
                    int ci = l;
                    if (r <= size && maxEle[l].w < maxEle[r].w) ci = r;
                    swap(maxEle, maxMap, cur, ci);
                    cur = ci;
                } else {
                    break;
                }
            }
        }

        //第k个元素下沉，小顶堆
        private void minSink(int k) {
            int cur = k;
            while (cur <= size / 2) {
                int l = cur << 1, r = cur << 1 | 1;
                if (minEle[l].w < maxEle[cur].w || (r <= size && minEle[r].w < minEle[cur].w)) {
                    int ci = l;
                    if (r <= size && minEle[l].w > minEle[r].w) ci = r;
                    swap(minEle, minMap, cur, ci);
                    cur = ci;
                } else {
                    break;
                }
            }
        }

        public void incr(String key) {
            //检查是否存在这个key，如果不存在就add，如果存在得到索引
            int idx1 = maxMap.getOrDefault(key, -1), idx2 = minMap.getOrDefault(key, -1);
            if (idx1 == -1) {
                add(new Node(key, 1));
            } else {
                maxEle[idx1].w++;
                //下面两个方法真正执行的只有一个
                maxSink(idx1);
                maxSwim(idx1);

                minSink(idx2);
                minSwim(idx2);
            }
        }

        public void decr(String key) {
            int idx1 = maxMap.get(key), idx2 = minMap.get(key);
            maxEle[idx1].w--;
            //如果减少到了0，就需要执行删除操作，否则直接调整
            if (maxEle[idx1].w == 0) {
                swap(maxEle, maxMap, idx1, size--);
                maxSwim(idx1);
                maxSink(idx1);
                //哈希表标记已经删除
                maxMap.put(key, -1);
                //删除小顶堆的元素
                swap(minEle, minMap, idx2, size + 1);
                minSwim(idx2);
                minSink(idx2);
                minMap.put(key, -1);
            } else {
                maxSink(idx1);
                maxSwim(idx1);
                minSink(idx2);
                minSwim(idx2);
            }
        }

        public String getMax() {
            if (size == 0) return "";
            return maxEle[1].key;
        }

        public String getMin() {
            if (size == 0) return "";
            return minEle[1].key;
        }

        public void add(Node node) {
            size++;
            maxEle[size] = minEle[size] = node;
            maxMap.put(node.key, size);
            minMap.put(node.key, size);
            maxSwim(size);
            minSwim(size);
        }

        private void swap(Node[] ele, Map<String, Integer> map, int i, int j) {
            Node temp1 = ele[i], temp2 = ele[j];
            map.put(temp1.key, j);
            map.put(temp2.key, i);
            ele[i] = ele[j];
            ele[j] = temp1;
        }
    }

    private static class Node {
        private String key;
        private int w;

        public Node(String key, int w) {
            this.key = key;
            this.w = w;
        }
    }
}
